package com.example.leetcode.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

//回溯
/**
 * 字符串的排列
 * 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
 * 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
 * <p>
 * <p>
 * 这是一个典型的排列问题，形如“给定一组数据，求这些数据所有的排列情况”，在这里一组数据就是字符串的字符。
 * 字符串的排列情况就是，每次需要选择一个字符（不能重复选择），按照顺序将选择的字符连接起来，可以用如下的树结构来描述选择情况。
 * <p>
 * 针对排列问题，就是做选择的过程，我们需要进行n次选择，每次需要记录选择的数据且不能重复选择，具体过程如下：
 * 1.遍历字符串中的字符，选择一个下标未加入过的字符（因为有重复不能比较字符值）加入记录中；
 * 2.重复1过程，直到字符串中的字符都加入到了记录中；
 * 3.撤销上一次的选择，选择上一次选择的下一个字符，并重复1,2；
 * 4.直到上一次选择的下一个字符为空，选择过程结束。
 * 在求排列的代码实现中，常使用回溯的方式，实现上述过程的回溯框架如下：
 * // 排列结果
 * List<String> res;
 * // 字符数组chars，选择数据记录memo
 * backtrack(char[] chars, StringBuilder memo){
 * if(memo.length() == chars.length && res中没有memeo){
 * /将memo加入到res中，并返回
 * }
 * for(int i=0;i<chars.length;i++){
 * if(memo中有chars[i]字符) 跳过；
 * memo.append(chars[i]);// 做选择，memo加入此字符
 * backtrack(chars, memo); //回溯
 * memo.deleteCharAt(memo.length()-1); // 撤销选择，返回上一次选择
 * }
 * }
 */
public class Permutation {

    public static void main(String[] args) {

        String str = "ABC";
        Permutation(str);


        String str1 = "ab";
//        permutation(str1);
    }

//    public static ArrayList<String> permutation(String str) {
//        if (str == null || str.length() == 0) {
//            return new ArrayList<>();
//        }
//
//
//        char[] charArray = str.toCharArray();
//        swap(charArray);
//
//        return res;
//    }

//    static ArrayList<String> res = new ArrayList<>();
//
//    private static void swap(char[] charArray) {
//        String s = "";
//        for (Character c : charArray) {
//            s = s + c.toString();
//        }
//        if (res.contains(s)) {
//            return;
//        }
//        res.add(s);
//        swap(c1, c2, c3);
//        swap(c2, c1, c3);
//        swap(c3, c2, c1);
//    }


    static ArrayList<String> result = new ArrayList<>();

    public static ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
            return result;
        }
        char[] charStr = str.toCharArray();
        // 按字典序排序
        Arrays.sort(charStr);
        // 存储字符顺序
        StringBuilder track = new StringBuilder();
        // 存储已经访问的字符下标
        HashMap<Integer, Character> map = new HashMap<>();
        // 回溯遍历
        backtrack(charStr, track, map);
        return result;
    }

    // 回溯法
    public static void backtrack(char[] charStr, StringBuilder track, HashMap<Integer, Character> map) {
        // 当字符数量等于字符数组长度时，才是一个完整的排列
        if (track.length() == charStr.length) {
            // 因为有重复字符串，需要去重
            if (!result.contains(track.toString())) {
                result.add(track.toString());
            }
            return;
        }
        // 每次都从0下标开始遍历
        for (int i = 0; i < charStr.length; i++) {
            if (map.containsKey(i)) {
                // 排除已选择的序号（不能直接用值）
                continue;
            }
            // 做选择
            track.append(charStr[i]);
            map.put(i, charStr[i]);
            // 回溯
            backtrack(charStr, track, map);
            // 撤销选择
            track.deleteCharAt(track.length() - 1);
            map.remove(Integer.valueOf(i));
        }
    }

}
